/**
 * @version Create on 2012-11-2
 * @author Yinzi Chen
 */

public class InterleavingString {

	public boolean isInterleave(String s1, String s2, String s3) {
		int m = s1.length(), n = s2.length(), r = s3.length();
		if (m + n != r)
			return false;
		if (r == 0)
			return true;
		if (m == 0)
			return s2.equals(s3);
		if (n == 0)
			return s1.equals(s3);
		boolean[][] d = new boolean[m + 1][n + 1];
		for (int i = 0; i <= m; ++i)
			d[i][0] = s1.subSequence(0, i).equals(s3.substring(0, i));
		for (int i = 0; i <= n; ++i)
			d[0][i] = s2.subSequence(0, i).equals(s3.substring(0, i));
		for (int i = 1; i <= m; ++i)
			for (int j = 1; j <= n; ++j) {
				if (d[i - 1][j] && s1.charAt(i - 1) == s3.charAt(i + j - 1)) {
					d[i][j] = true;
				} else if (d[i][j - 1]
						&& s2.charAt(j - 1) == s3.charAt(i + j - 1)) {
					d[i][j] = true;
				}
			}
		return d[m][n];
	}

	public static void main(String[] args) {
		InterleavingString a = new InterleavingString();
		a.isInterleave("", "b", "b");
	}

}
